정보처리학회 논문지 D
Current Result Document :
| 한글제목(Korean Title) |
H*-tree/H*-cubing: 데이터 스트림의 OLAP를 위한 향상된 데이터 큐브 구조 및 큐빙 기법 |
| 영문제목(English Title) |
H*-tree/H*-cubing: Improved Data Cube Structure and Cubing Method for OLAP on Data Stream |
| 저자(Author) |
심상예
이 연
이동욱
김경배
배해영
Xiangrui Chen
Yan Li
Dong-Wook Lee
Gyoung-Bae Kim
Hae-Young Bae
|
| 원문수록처(Citation) |
VOL 16-D NO. 04 PP. 0475 ~ 0486 (2009. 08) |
한글내용
(Korean Abstract) |
데이터 큐브는 다차원 데이터 분석 및 멀티레벨 데이터 분석에 많이 사용되고 있는 중요한 데이터 구조이다. 최근 데이터 스트림의 온라인 분석에 대한 수요가 증가하면서 스트림 큐브, Flow 큐브, S-큐브 등의 다양한 데이터 큐브 구조와 기법이 제안되었다. 그러나 기존 기법들은 데이터 큐브 생성 시 고비용이 요구되는 단점을 가지고 있어 효과적인 데이터 구조, 질의 방법 및 알고리즘에 대한 연구가 필요하다. 스트림 큐브 기법에서는 H-큐빙 기법을 사용하여 큐보이드를 선택하고, 계산된 셀들을 인기 패스에 있는 큐보이드들로 구성된 H-트리에 저장한다. 그러나 스트림 큐브 기법에서는 H-트리에 데이터를 비순차적으로 삽입하기 때문에 H-큐빙 기법을 사용하여 질의를 처리할 때 제한성을 갖고 있다. 본 논문에서는 데이터의 트리 구조의 각 층에 대한 인덱스를 구축하여 스트림 데이터에 대한 빠른 삽입 연산을 지원하는 H*-tree 구조와, popular-path에 존재하지 않는 큐보이드를 빨리 계산하여 스트림 데이터에 대한 빠른 애드 혹 질의 응답을 지원하는 H*-cubing 기법을 제안한 다. 성능평가를 통하여 제안한 H*-tree 기법은 보다 적은 큐브 구축 시간을 지원하며, H*-cubing 기법이 stream cube 기법보다 빠른 애드 혹 질의 응답 시간을 소요하며, 보다 적은메모리를 사용함을 보여준다. |
영문내용
(English Abstract) |
Data cube plays an important role in multi-dimensional, multi-level data analysis. Meeting on-line analysis requirements of data stream, several cube structures have been proposed for OLAP on data stream, such as stream cube, flowcube, S-cube. Since it is costly to construct data cube and execute ad-hoc OLAP queries, more research works should be done considering efficient data structure, query method and algorithms. Stream cube uses H-cubing to compute selected cuboids and store the computed cells in an H-tree, which form the cuboids along popular-path. However, the H-tree layoutis disorderly and H-cubing method relies too much on popular path.In this paper, first, we propose H*-tree, an improved data structure, which makes the retrieval operation in tree structure more efficient. Second, we propose an improved cubing method, H*-cubing, with respect to computing the cuboids that cannot be retrieved along popular-path when an ad-hoc OLAP query is executed. H*-tree construction and H*-cubing algorithms are given. Performance study turns out that during the construction step, H*-tree outperforms H-tree with a more desirable trade-off between time and memory usage, and H*-cubing is better adapted to ad-hoc OLAP querieswith respect to the factors such as time and memory space. |
| 키워드(Keyword) |
OLAP
데이터 스트림
데이터 큐브
Ad-Hoc질의 처리
On-line Analytic Processing(OLAP)
Data Stream
Data Cube
Ad-Hoc Query Answering
|
| 파일첨부 |
PDF 다운로드
|
